#include <vector>
using namespace std;
/*
 * @lc app=leetcode.cn id=81 lang=cpp
 *
 * [81] 搜索旋转排序数组 II
 */

// @lc code=start
class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int l = 0, r = nums.size(); // [ )
        while (r - l > 1) {
            int middle = (r + l) / 2;
            if (nums[middle] == target) return true;
            else if (nums[middle] < target) {
                if (target == nums[l]) return true;
                if (target > nums[l] && nums[middle] < nums[l])
                    r = middle;
                else
                    l = middle + 1; 
            }
            else {
                if (target == nums[l]) return true;
                if (target < nums[l] && nums[middle] >= nums[l])
                    l = middle + 1;
                else
                    r = middle; 
            }
        }
        return nums[l] == target;
    }
};
// @lc code=end

